#include "cartesian_tree.hpp"
#include <cstdlib>
#include <cstdio>
inline CTe::CTe(entry obj) {x=obj.hash();data=obj;y=(rand()<<16)+rand();l=r=NULL;norm(this);}

CT::CT() {
	tree=0;
}

void CT::ins(entry obj) {
//	printf("CT insertion started\n");
	CTe *nw=new CTe(obj);
	CTe *lt;
	split(lt,tree,tree,nw->x);
	merge(lt,nw,lt);
	merge(lt,tree,tree);
}

void CT::del(entry obj) {
	CTe *lt,*rt;
	split(lt,rt,this->tree,obj.hash());
	split(lt,this->tree,lt,obj.hash()-1);
	while (this->tree) {
		CTe *tk;
		spliti(tk,this->tree,this->tree,1);
		if (tk->data!=obj) merge(lt,tk,lt);
		else delete tk;
	}
	merge(lt,rt,this->tree);
}

void CT::gen_list(list<entry> &l) {
	tree->gen_list(l);
}

void CTe::gen_list(list<entry> &lst) {
	if (l) l->gen_list(lst);
	lst.push_back(data);
	if (r) r->gen_list(lst);
}
  
void CT::clear() {
	tree->clear();
	delete tree;
}

void CTe::clear() {
	if (l) {
		l->clear();
		delete l;
	}
	if (r) {
		r->clear();
		delete r;
	}
}

bool CT::isempty() {
	return tree==NULL;
}

void norm(CTe *t) {
	if (!t) return;
	t->c=1;
	if (t->l) {t->c+=t->l->c;}
	t->ix=t->c;
	if (t->r) {t->c+=t->r->c;}
}

void split(CTe *&l,CTe *&r,CTe *t,int k) {
	if (!t) {l=NULL;r=NULL;return;}
	norm(t);
	if (t->x<=k) {
		l=t;
		spliti(t->r,r,t->r,k-t->ix);
		norm(t->r);
	} else {
		r=t;
		spliti(l,t->l,t->l,k);
		norm(t->l);
	}
	norm(l);
	norm(r);
}

void spliti(CTe *&l,CTe *&r,CTe *t,int k) {
	if (!t) {l=NULL;r=NULL;return;}
	norm(t);
	if (t->ix<=k) {
		l=t;
		spliti(t->r,r,t->r,k-t->ix);
		norm(t->r);
	} else {
		r=t;
		spliti(l,t->l,t->l,k);
		norm(t->l);
	}
	norm(l);
	norm(r);
}

void merge(CTe *l,CTe *r,CTe *&t) {
	if (!l) t=r; else if (!r) t=l; else {
		if (l->y<r->y) {
			t=l;
			merge(l->r,r,l->r);
			norm(l->r);
		} else {
			t=r;
			merge(l,r->l,r->l);
			norm(r->l);
		}
	}
	norm(t);
}
